package _02array;

/**
 * Created by Enzo Cotter on 2021/2/19.
 */
// bubble sort
// time complexity: O(n^2)
// space complexity: O(1)
public class _09BubbleSortSpeed {
    void bubbleSort(int arr[]) {

        int n = arr.length;

        for (int i = 0; i < n-1; i++) {
            int flag = 0;
            for (int j = 0; j < n - 1 - i ; j++)
                if (arr[j] > arr[j + 1]) {
                    // speed
                    flag = 1;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            if(flag == 0)
                return ;
        }

    }

    public static void main(String args[]) {

        _09BubbleSortSpeed bs = new _09BubbleSortSpeed();
//        int arr[] = {1, 2, 4, 11, 23, 77, 80};
//        int arr[] = {1, 2, 4, 11, 80, 23, 77};
        int arr[] = {3, 33, 14, 11, 23, 10, 80};

        // bubble sort speed
        bs.bubbleSort(arr);

        for(int i : arr)
            System.out.print(i + " ");
    }
}
